//给你一个整数数组 nums，请你将该数组升序排列。 
//
// 
//
// 
// 
//
// 示例 1： 
//
// 输入：nums = [5,2,3,1]
//输出：[1,2,3,5]
// 
//
// 示例 2： 
//
// 输入：nums = [5,1,1,2,0,0]
//输出：[0,0,1,1,2,5]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 50000 
// -50000 <= nums[i] <= 50000 
// 
// 👍 155 👎 0

package leetcode.editor.cn;

import java.lang.reflect.Array;
import java.util.Arrays;

//Java：排序数组
public class P912SortAnArray {
    public static void main(String[] args) {
        Solution solution = new P912SortAnArray().new Solution();
        int []arr = {9,8,7,6,5,4,3,2,1};
        solution.sortArray(arr);
        System.out.println(Arrays.toString(arr));
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[] sortArray(int[] nums) {
            //构建大顶堆
            for (int i = nums.length / 2 - 1; i >= 0; i--) {//从第一个非叶子节点调整，从左往右从上往下，第一个非叶子节点nums.length/2-1
                adjustHeap(nums, i, nums.length);
            }

            //调整堆结构+交换堆顶元素与末尾元素
            for(int j=nums.length-1;j>0;j--){
                swap(nums,0,j);
                adjustHeap(nums,0,j);
            }


            return nums;
        }


        private void swap(int[] nums, int i, int j) {
            int tmp=nums[i];
            nums[i]=nums[j];
            nums[j]=tmp;
        }

        private void adjustHeap(int[] nums, int i, int length) {
            int tmp=nums[i];//取出当前元素i
            for(int k=i*2+1;k<length;k=k*2+1){//从i节点的左子节点开始，也就是2i+1处开始
                if(k+1<length&&nums[k]<nums[k+1]){//如果左子节点小于右子节点，k指向右子节点
                    k++;
                }
                if(nums[k]>tmp){
                    nums[i]=nums[k];
                    i=k;
                }else{
                    break;
                }

            }
            nums[i]=tmp;//将tmp值放到最终的位置
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
